1. Field of the Invention
The present invention generally relates to image processing systems and, more particularly, to image processing systems capable of finding visible points or fragments that are connected by a line segment to the eyepoint that meets the closure of no other primitive within the same scene.
2. Background Description
In a given scene, , finding visible points or fragments that are connected to the eyepoint by a line segment that meets the closure of no other primitive within the same scene is a well known image processing problem. This visibility problem is discussed by D. Dobkin and S. Teller xe2x80x9cComputer Graphics,xe2x80x9d Handbook of Discrete and Computational Geometry, chapter 42, pages 779-96. CRC Press, Boca Raton, Fla., 1997 (hereinafter Dobkin).
As described in Dobkin, the scene, , is composed of modeling primitives (e.g., triangles, or spheres), and a viewing frustum defining an eye position, a view direction, and a field of view. For any scene with n primitives, the complexity of the set of visible fragments might be quadratic as a function of n. One well known approach to solving this visibility problem is the Z-buffer algorithm of E. Catmull as described in xe2x80x9cA Subdivision Algorithm for Computer Display of Curved Surfacesxe2x80x9d, PhD thesis, Dept. of Computer Science, University of Utah, December 1974.
The Z-buffer algorithm exploits the discrete nature of the screen to solve the visibility problem in time proportional to n, because it only touches each primitive once. The Z-buffer algorithm solves the visibility problem by maintaining a depth value for each pixel and, only updating the pixels when rendering geometry closer to the eyepoint. For high-depth complexity scenes, the Z-buffer algorithm might result in overdrawing each pixel a considerable number of times. However, despite this potential inefficiency, the Z-buffer is a popular algorithm and widely implemented in hardware.
Given the wide availability of the Z-buffer approach but with exact visibility computations potentially being too costly in terms of computer time and associated hardware costs, alternative approaches are being sought. One approach is to use the Z-buffer as a filter and design algorithms that compute an approximation of the visible set to reduce the amount of overdraw. More precisely, the visible set  (a subset of ) is defined to be a set of modeling primitives that contribute at least one pixel to the screen. In computer graphics, visibility-culling research has focused, mainly, on algorithms for computing estimations of , then, obtaining correct images using the Z-buffer.
The simplest examples of visibility-culling algorithms are the xe2x80x9cbackfacexe2x80x9d and xe2x80x9cview-frustumxe2x80x9d algorithms, as described by Foley et al. xe2x80x9cComputer Graphics, Principles and Practice, Second Edition,xe2x80x9d Addison-Wesley, Reading, Mass., 1990. Backface-culling algorithms avoid rendering geometric primitives that face away from the viewer; while viewing-frustum culling algorithms avoid rendering geometric primitives that are outside of the viewing frustum.
Still another approach is using hierarchical occlusion maps as described by Zhang et al. in xe2x80x9cVisibility Culling Using Hierarchical Occlusion Maps,xe2x80x9d SIGGRAPH 97 Conference Proceedings, pages 77-88, 1997. The hierarchical occlusion map approach solves the visibility problem by using two hierarchies, an object-space bounding volume hierarchy and another hierarchy of image space occlusion maps. A set of objects (occluders) are selected for each frame from a pre-computed database. The occluders are used to cull unseen geometric primitives. Closely related to this technique is the hierarchical Z-buffer described in U.S. Pat. No. 5,579,455 entitled xe2x80x9cRendering of 3d Scenes on a Display Using Hierarchical Z-buffer Visibilityxe2x80x9d to Greene et al., which is incorporated herein by reference.
Yet another approach is object-space visibility culling. One such object-space visibility culling technique, described by Teller and Sequin in xe2x80x9cVisibility Preprocessing for Interactive Walkthroughs,xe2x80x9d Computer Graphics, pages 61-69, July 1991 (hereinafter Teller). Teller teaches dividing space into cells and, then, preprocessing the cells for potential visibility. The Teller technique works particularly well for architectural models. These state of the art visibility-culling techniques mostly exploit the presence of large occluders, and keep track of spatial extents over time.
In yet another approach, Funkhouser and Sequin in xe2x80x9cAdaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments,xe2x80x9d Computer Graphics, pp. 247-54, 1993, describe a constant-frame rendering system.
However, all of the above state of the art techniques for occlusion-culling have several drawbacks. First of all, the simple backface and viewing-frustum culling algorithms of Foley et al. are unable to cull xe2x80x9coverdrawxe2x80x9d geometry. For this type of culling, more complex techniques that lead to substantial improvements in rendering time are needed. Unfortunately, these techniques for tighter estimation of the visible set do not come easily. Most currently proposed techniques are quite involved and complex, typically requiring computation of complex object hierarchies in both 3- and 2- space.
In addition to the above problems, typically, a significant portion of the geometric primitives that are not visible are not culled by the prior art occlusion culling methods. Further, these prior art methods do not allow a user-defined budget to be used for culling, e.g., specifying a limit on the number of primitives to render, and therefore, these prior art methods are not time-critical.
Thus, there is a need for more efficient rendering techniques for optimizing the rendering of high-depth complexity scenes.
It is therefore a purpose of the present invention to efficiently select geometric primitives to be rendered in an image;
It is another purpose of the present invention to efficiently select geometric primitives to be rendered within an image processing system""s budget constraints;
It is yet another purpose of the present invention to efficiently select geometric primitives to be rendered within an image processing system""s time constraints.
The present invention is a Prioritized-Layered Projection (PLP) technique and system for optimizing the rendering of high-depth complexity scenes. Objects in each frame are prioritized with an estimation of the visible set within the rendered frame. Visible sets are not explicitly computed, but, instead, a priority order is computed xe2x80x9con demandxe2x80x9d to maximize the likelihood of rendering visible primitives before rendering occluded ones. For a fixed budget, e.g., time or number of triangles, the rendering technique of the present invention constrains that geometry rendering to the budgeted priority.
The preferred embodiment of the present invention includes two main steps: (1) an occupancy-based tessellation of space; and (2) a solidity-based traversal algorithm. By first computing an occupancy-based tessellation of space, more cells result where there are more geometric primitives. In this spatial tessellation, each cell is assigned a xe2x80x9csolidityxe2x80x9d value directly proportional to its likelihood of occluding other cells. In its simplest form, a cell""s solidity value is directly proportional to the number of primitives contained within the cell. Cells are marked for projection, and the geometric primitives contained within the marked cells are rendered. The present invention uses the cells solidity and other view-dependent information to determine the ordering in which to project cells.